// 哈希表
/*
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        unordered_map<int, int> hashtable;
        for (int i = 0; i < numbers.size(); i++) {
            auto it = hashtable.find(target - numbers[i]);
            if (it != hashtable.end()) {
                return {it->second + 1, i + 1};
            }
            hashtable[numbers[i]] = i;
        }
        return {};
    }
};
*/

// 双指针
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        while (true) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) return {left + 1, right + 1};
            else if (sum < target) left++;
            else right--;
        }
        return {};
    }
};